package com.jack.leetcode.eachproblem_2020;

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

/**
 * Created by zhang_j on 2020/10/23
 */
public class LFUCache {

    class Node{
        int key, value, freq;
        Node prev, next;
        Node(int key, int value, int freq){
            this.key = key;
            this.value = value;
            this.freq = freq;
        }
    }

    class DLinkedList{
        Node head, tail;
        DLinkedList(){
            head = tail = null;
        }
        public void remove(Node node){
            if(node == head){
                head = head.next;
            }
            if(node == tail){
                tail = tail.prev;
            }
            Node prev = node.prev;
            Node next = node.next;
            if(prev != null){
                prev.next = next;
            }
            if(next != null){
                next.prev = prev;
            }
            node.prev = node.next = null;
        }
        public void removeTail(){
            if(tail == null){
                return;
            }
            if(tail == head){
                head = tail = null;
                return;
            }
            tail = tail.prev;
            tail.next.prev = null;
            tail.next = null;
        }
        public Node getTail(){
            return tail;
        }
        public void insertToHead(Node node){
            if(head == null){
                head = tail = node;
                return;
            }
            head.prev = node;
            node.next = head;
            node.prev = null;
            head = node;
        }
        public boolean isEmpty(){
            return head == null;
        }
    }

    private volatile  Map<Integer, Node> keyMap;
    private volatile  Map<Integer, DLinkedList> freqMap;
    private volatile int size, capacity;
    private volatile int minFreq;
    public LFUCache(int capacity){
        keyMap = new ConcurrentHashMap<>();
        freqMap = new ConcurrentHashMap<>();
        this.capacity = capacity;
        minFreq = Integer.MAX_VALUE;
    }

    public int get(int key){
        if(capacity < 1){
            return -1;
        }
        Node node = keyMap.get(key);
        if(node == null){
            return -1;
        }
        updateFreqMap(node);
        return node.value;
    }

    public synchronized void put(int key, int value){
        if(capacity < 1){
            return;
        }
        Node node = keyMap.get(key);
        if(node == null){
            node = new Node(key, value, 1);
            if(size == capacity){
                --size;
                DLinkedList dLinkedList = freqMap.get(minFreq);
                keyMap.remove(dLinkedList.getTail().key);
                dLinkedList.removeTail();
            }
            size++;
            DLinkedList compute = freqMap.computeIfAbsent(1, x -> new DLinkedList());
            compute.insertToHead(node);
            keyMap.put(key, node);
            minFreq = 1;
        }else{
            node.value = value;
            updateFreqMap(node);
        }
    }

    private void updateFreqMap(Node node){
        DLinkedList dLinkedList = freqMap.get(node.freq);
        dLinkedList.remove(node);
        if(minFreq == node.freq && dLinkedList.isEmpty()){
            minFreq += 1;
        }
        node.freq += 1;
        DLinkedList newDList = freqMap.computeIfAbsent(node.freq, x -> new DLinkedList());
        newDList.insertToHead(node);

    }
}
